1. Field of the Invention
The invention relates to computer systems, and more particularly to dependency tracking in a database system.
2. Background
The present invention pertains to dependency tracking in a database system. xe2x80x9cDependencyxe2x80x9d in a database system refers to the ordering in which operations may be performed against data items in the database. If a first operation is applied against a data item, and a second operation against that data item can only be applied after the first operation has been completed, then the second operation is said to be dependent upon the first operation. For example, consider a database statement to xe2x80x9cUPDATExe2x80x9d a data item. That statement can only be processed after a prior statement to xe2x80x9cINSERTxe2x80x9d that data item into a database has completed (since the data item does not exist until the completion of the INSERT statement). Thus, the UPDATE statement in this example is dependent upon the INSERT statement.
A logical unit of work in a database system that comprises one or more database statements is often referred to as a transaction. When a database system executes a transaction, the transaction may perform a data operation upon a data item that was written or updated in response to the execution of previous transaction(s). Consequently, the results returned by the database system in response to executing any given transaction are dictated by changes made by a set of previously executed transactions. With respect to affected data items, the latest transaction is thus dependent upon previous transactions that have operated upon those data items.
For many reasons, it is useful to track dependencies between transactions in a database system. For example, assume that two transactions, TXA and TXB, must be reapplied to the database. This may occur, for example, if the database is recovering from a prior database failure and transactions are being reapplied to set the database back to its pre-failure state. As an another example, tracking dependencies is useful in determining the order in which transactions may be applied or propagated when replicating a database.
Dependency tracking is also useful with respect to database objects having uniqueness constraints. For a relational database table, a uniqueness constraint requires that every value in a column or set of columns to be uniquexe2x80x94that is, no two rows of a table should have duplicate entries in a specified column or set of columns. For example, assume that a first transaction deletes a row from a table having a key value in a xe2x80x9cuniquenessxe2x80x9d column and a second transaction adds a new and different row to the table having the same key value in that column. The second transaction is dependent upon the execution and completion of the first transaction, since otherwise, there would be two rows in the table having the same key value in the column, which would violate the uniqueness constraint upon the column.
Dependency information can be extracted from log files in a database system. However, extracting and analyzing log files to determine/track dependencies is a very expensive to perform. Therefore, it is clearly desirable to provide a method and mechanism to track dependencies in a database statement.
The present invention is directed to a method and mechanism for dependency tracking in a database system. According to an embodiment of the invention, all dependencies for a transaction or operation can be characterized by a single value representing all prior transactions or database changes that it is dependent upon. This value can be calculated at various granularity levels, such as the granularity of the row level, based upon maintaining a data structure that records change or commit values for a specified granularity level for objects in a database. For granularity at the row level, a row_SCN value can be maintained according to an embodiment of the invention.
According to an aspect of an embodiment of the invention, dependency tracking is performed for uniqueness constrained objects by tracking change or commit values for a key range associated with the uniqueness constrained object. For uniqueness constrained tables, this type of key range can be associated with a particular column or set of columns in the uniqueness constrained table. If an index exists upon a uniqueness constrained column, then the key range can correspond to a range of index key values.
According to another aspect of an embodiment of the invention, dependency tracking for referentially constrained objects is performed by tracking change or commit values for certain key ranges as well as change or commit values at various granularities in the database. The combination of the various sets of change or commit values are employed to determine a single value representing all prior transactions or database changes that an operation or transaction is dependent upon.